package com.lisp.algorithm.leetcode;

import com.lisp.algorithm.util.ArrayUtil;

public class BinarySearch {

	public static void main(String[] args) {
		int a[] = {0, 10, 10, 20};
		ArrayUtil.print(binarySearch(a, 0, a.length-1, 20));
		
		ArrayUtil.print(binarySearch(a, 20));
	}
	
	private static int[] binarySearch(int a[], int aStart, int aEnd, int val) {
		if(aStart > aEnd) {
			return new int[]{-1};
		}
		
		int middle = (aStart + aEnd) / 2;
		if(a[middle] == val) {
			int i=middle-1;
			while(i >= aStart && a[i] == val) {
				i--;
			}
			
			int j=middle+1;
			while(j <= aEnd && a[j] == val) {
				j++;
			}
			return new int[] {i+1, j-1};
		} else if(a[middle] < val) {
			return binarySearch(a, middle+1, aEnd, val);
		} else {
			return binarySearch(a, aStart, middle-1, val);
		}
	}
	
	private static int[] binarySearch(int a[], int val) {
		int aStart = 0, aEnd = a.length-1;
		while(aStart <= aEnd) {
			int middle = (aStart + aEnd) / 2;
			if(a[middle] == val) {
				int i=middle-1;
				while(i >= aStart && a[i] == val) {
					i--;
				}
				
				int j=middle+1;
				while(j <= aEnd && a[j] == val) {
					j++;
				}
				return new int[] {i+1, j-1};
			} else if(a[middle] < val) {
				aStart = middle + 1;
			} else {
				aEnd = middle - 1;
			}
		}
		return new int[] {-1};
	}
}
